/**
 * 
 */
package com.gwcloud.leetcode.hot100;

/**
 * @ClassName   : Leetcode0416 
 * @author      : ganwei 
 * @date        : 2020年5月23日
 * @Description : Leetcode0416
 */
public class Leetcode0416 {
	/**
	 * -解题思路,回溯，超时
	 */
    public boolean canPartition(int[] nums) {
    	int sum = 0;
    	for(int i = 0; i < nums.length; i++){
    		sum += nums[i];
    	}
    	if(sum % 2 != 0){
    		return false;
    	}
    	return backtrace(nums, 0, 0, sum);
    }
    /**
     * -回溯主题
     */
    public boolean backtrace(int[] nums, int start, int cursum, int sum) {
    	if(cursum * 2 == sum){
    		return true;
    	}
    	if(start == nums.length){
    		return false;
    	}
    	for(int i = start; i < nums.length; i++){
    		if(backtrace(nums, i+1, cursum+nums[i],sum)){
    			return true;
    		}
    	}
    	return false;
    }
    /**
     * -动态规划
     */
    public boolean canPartition_1(int[] nums) {
    	int sum = 0;
    	for(int num : nums){
    		sum += num;
    	}
    	
    	if(sum % 2 != 0){
    		return false;
    	}
    	int target = sum / 2;
    	boolean[] dp = new boolean[target+1];
    	dp[0] = true;
    	for(int num : nums){
    		for(int i = target; i >= num; i--){
    			if(dp[i-num] == true){
    				dp[i] = true;
    			}
    		}
    	}
    	
    	
    	return dp[target];
    }
    /**
     * -主函数
     */
    public static void main(String[] args){
    	int[] nums = {1, 5, 11, 5};
    	Leetcode0416 l0416 = new Leetcode0416();
    	System.out.println(l0416.canPartition(nums));
    }
}
